    /*
     * 不同的子序列
     * String S    String T
     * 状态：F(i,j) 是S的前i个字符的子序列与 T的前j个字符 相同的个数
     * 状态转移方程：如果 S[i] ==T[j]
     *            F[i,j] = F[i-1,j-1] + F[i-1,j]
     *            如果 S[i] != T[j]
     *            F[i,j] = F[i-1,j]
     * 初始状态： F[0][0] = 1;
     *          F[0][j] = 0 (j!=0);
     *          F[i][0] = 0;
     * */
    public class Solution {
        public int numDistinct(String S, String T) {
            int lenS = S.length();
            int lenT = T.length();
            int[][] numDis = new int[lenS + 1][lenT + 1];
            for (int i = 0; i <= lenS; i++) {
                numDis[i][0] = 1;
            }
            for (int i = 1; i <= lenS; i++) {
                for (int j = 1; j <= lenT; j++) {
                    if (S.charAt(i - 1) == T.charAt(j - 1)) {
                        numDis[i][j] = numDis[i - 1][j - 1] + numDis[i - 1][j];
                    } else {
                        numDis[i][j] = numDis[i - 1][j];
                    }
                }
            }
            return numDis[lenS][lenT];
        }
    }